#include <stdio.h>
#define V 4    
#define INF 65535   
int P[V][V] = { 0 }; 
void printMatrix(int matrix[][V]);  
void printPath(int i, int j); 
void floydWarshall(int graph[][V]); 
int main() {
    int graph[V][V] = { {0, 3, INF, 5},
                          {2, 0, INF, 4},
                          {INF, 1, 0, INF},
                          {INF, INF, 2, 0} };
    floydWarshall(graph);
}
void printPath(int i, int j)
{
    int k = P[i][j];
    if (k == 0)
        return;
    printPath(i, k);
    printf("%d-", k + 1);
    printPath(k, j);
}
void printMatrix(int graph[][V]) {
    int i, j;
    for (i = 0; i < V; i++) {
        for (j = 0; j < V; j++) {
            if (j == i) {
                continue;
            }
            printf("%d - %d: 最短路径为:", i + 1, j + 1);
            if (graph[i][j] == INF)
                printf("%s\n", "INF");
            else {
                printf("%d", graph[i][j]);
                printf("，依次经过：%d-", i + 1);
                printPath(i, j);
                printf("%d\n", j + 1);
            }
        }
    }
}
void floydWarshall(int graph[][V]) {
    int  i, j, k;
    for (k = 0; k < V; k++) {
        for (i = 0; i < V; i++) {
            for (j = 0; j < V; j++) {
                if (graph[i][k] + graph[k][j] < graph[i][j]) {
                    graph[i][j] = graph[i][k] + graph[k][j];
                    P[i][j] = k;
                }
            }
        }
    }
    printMatrix(graph);
}

